package MyLinkedList;

public class MylinkedList {
	static class ListNode {
		private int val;
		private ListNode prev;
		private ListNode next;

		public ListNode(int val) {
			this.val = val;
		}
	}
	public ListNode head;
	public ListNode last;
	public int size() {
		ListNode cur=head;
		int cnt=0;
		while(cur!=null) {
			cnt++;
			cur=cur.next;
		}
		return cnt;
	}
	public void display() {
		ListNode cur=head;
		while(cur!=null) {
			System.out.print(cur.val+" ");
			cur=cur.next;
		}
		System.out.println();
	}
	public boolean contains(int key) {
		ListNode cur=head;
		while(cur!=null) {
			if (cur.val == key) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}
	//头插
	public void addFirst(int data) {
		ListNode node=new ListNode(data);
		if(head==null) {
			head=node;
			last=node;
			return;
		}
		//不为空
		node.next=head;
		head.prev=node;
		head=node;
	}
	//尾插
	public void addLast(int data ) {
		ListNode node=new ListNode(data);
		if(head==null) {
			addFirst(data);
			return ;
		}
		//不为空的话
		//找到最后一个，在进行插入
		ListNode cur=head;
		while(cur.next!=null) {
			cur=cur.next;
		}
		cur.next=node;
		node.prev=cur;
		last=node;
	}
	public void addIndex(int index,int data) {
		checkIndex(index);
		if(index==0) {
			addFirst(data);
			return;
		}
		if(index==size()) {
			addLast(data);
			return;
		}
		ListNode cur=searchListNode(index);
		ListNode node=new ListNode(data);
		cur.prev.next=node;
		node.next=cur;
		node.prev=cur.prev;
		cur.prev=node;
	}
	private void checkIndex(int index) {
		if(index<0||index>size()) {
			throw new IndexOutofException("位置不合法"+index);
		}
	}
	private ListNode searchListNode(int index) {
		ListNode cur=head;
		while(index!=0) {
			cur=cur.next;
			index--;
		}
		return cur;
	}
	//删除第一个出现的节点
	public void remove (int key) {
		if(head==null) {
			return;
		}
		ListNode cur=head;
		while(cur!=null) {
			if(cur.val==key) {
				//这个节点可能出现的位置有头部，中间，尾部
				//再配合这个链表的长度进行判断，链表的长度可能是0，1，大于1。
				if(head.val==key)
				{
					head=head.next;
					//只有一个节点并且这个节点就是要找的，删除之后head为空，造成空指针异常
					if(head!=null) {
						head.prev=null;
					} else {
						//当程序走到这里的时候，说明只有一个节点并且这个节点就是我们要找的
						last=null;
					}
				} else {
					//当程序走到这里的时候，要进行尾删除和中间的节点删除
					//尾部的节点判断条件很简单，就是cur.next为空
					if(cur.next!=null) {
						cur.prev.next=cur.next;
						cur.next.prev=cur.prev;
					} else {
						cur.prev.next = cur.next;
						last = cur.prev;
					}
				}
				//这里代表是删除完毕，直接终止程序了
				return ;
			} else {
				cur=cur.next;
			}
		}
	}
	//删除重复出现的节点
	//重点
	public void removeAllkey(int key) {
		if(head==null) {
			return;
		}
		ListNode cur=head;
		while(cur!=null) {
			if(cur.val==key) {
				if(head.val==key)
				{
					head=head.next;
					if(head!=null) {
						head.prev=null;
					} else {
						last=null;
					}
				} else {
					if(cur.next!=null) {
						cur.prev.next=cur.next;
						cur.next.prev=cur.prev;
					} else {
						cur.prev.next = cur.next;
						last = cur.prev;
					}
				}
				//因为这是重复删除所以要进行一直删除
				//return ;
				cur=cur.next;
			} else {
				cur=cur.next;
			}
		}
	}
	public void clear() {
		ListNode cur=head;
		while(cur!=null) {
			ListNode curNext=cur.next;
			cur.next=null;
			cur.prev=null;
			cur=curNext;
		}
		head=null;
		last=null;
	}
}
